155 最小栈

https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnkq37/

https://leetcode.cn/problems/min-stack/description/

cost: 12m6s

class MinStack {
public:
    MinStack() : idx(0) {}

    void push(int val) {
        int minVal = val;
        if (idx != 0) {
            minVal = std::min(minVal, minNums[idx - 1]);
        }
        if (idx >= nums.size()) {
            nums.push_back(val);
            minNums.push_back(minVal);
        } else {
            nums[idx] = val;
            minNums[idx] = minVal;
        }
        idx++;
    }

    void pop() { idx--; }

    int top() { return nums[idx - 1]; }

    int getMin() { return minNums[idx - 1]; }

private:
    vector<int> nums;
    int idx;
    vector<int> minNums;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

• 时间复杂度：O(n)
• 空间复杂度：O(n)